/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/x-of-a-kind-in-a-deck-of-cards
   @Language: C++
   @Datetime: 19-05-28 14:50
   */

// Method 1, enum 2~x, Time 468ms
class Solution {
public:
	/**
	 * @param deck: a integer array
	 * @return: return a value of bool
	 */
	bool hasGroupsSizeX(vector<int> &deck) {
		// write your code here
		unordered_map<int,int> freqs;
		for(int i=deck.size(); i--; ++freqs[deck[i]]);
		int x=freqs.begin()->second;
		for(auto it=freqs.begin(); it!=freqs.end(); ++it)
			if(it->second<x) x=it->second;
		for(int k=2; k<=x; ++k){
			bool found=true;
			for(auto it=freqs.begin(); found && it!=freqs.end(); ++it)
				if(it->second%k) found=false;
			if(found) return true;
		}
		return false;
	}
};


// Method 2, gcd, Time 211ms
class Solution {
public:
	/**
	 * @param deck: a integer array
	 * @return: return a value of bool
	 */
	bool hasGroupsSizeX(vector<int> &deck) {
		// write your code here
		unordered_map<int,int> freqs;
		for(int i=deck.size(); i--; ++freqs[deck[i]]);
		int x=freqs.begin()->second;
		for(const auto &p:freqs){
			x=__gcd(x,p.second);	// c++17, gcd
			if(x==1) return false;
		}
		return true;
	}
};
